package leetcode.editor.cn.q1_300.q200;
//城市的 天际线 是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。给你所有建筑物的位置和高度，请返回 由这些建筑物形成的 天际线 。 
//
// 每个建筑物的几何信息由数组 buildings 表示，其中三元组 buildings[i] = [lefti, righti, heighti] 表示： 
//
//
// 
// lefti 是第 i 座建筑物左边缘的 x 坐标。 
// righti 是第 i 座建筑物右边缘的 x 坐标。 
// heighti 是第 i 座建筑物的高度。 
// 
//
// 你可以假设所有的建筑都是完美的长方形，在高度为 0 的绝对平坦的表面上。 
//
// 天际线 应该表示为由 “关键点” 组成的列表，格式 [[x1,y1],[x2,y2],...] ，并按 x 坐标 进行 排序 。关键点是水平线段的左端点。
//列表中最后一个点是最右侧建筑物的终点，y 坐标始终为 0 ，仅用于标记天际线的终点。此外，任何两个相邻建筑物之间的地面都应被视为天际线轮廓的一部分。 
//
// 注意：输出天际线中不得有连续的相同高度的水平线。例如 [...[2 3], [4 5], [7 5], [11 5], [12 7]...] 是不正确的答
//案；三条高度为 5 的线应该在最终输出中合并为一个：[...[2 3], [4 5], [12 7], ...] 
//
// 
//
// 示例 1： 
// 
// 
//输入：buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
//输出：[[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
//解释：
//图 A 显示输入的所有建筑物的位置和高度，
//图 B 显示由这些建筑物形成的天际线。图 B 中的红点表示输出列表中的关键点。 
//
// 示例 2： 
//
// 
//输入：buildings = [[0,2,3],[2,5,3]]
//输出：[[0,3],[5,0]]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= buildings.length <= 10⁴ 
// 0 <= lefti < righti <= 2³¹ - 1 
// 1 <= heighti <= 2³¹ - 1 
// buildings 按 lefti 非递减排序 
//

import leetcode.editor.cn.util.arr.ArrayUtil;

import java.util.*;
import java.util.stream.Collectors;

public class Q218_TheSkylineProblemBAK {
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 思路一：
     * 打散为一维数组，数组长度为 最左 left - 最右侧的 right
     * 将数组 buildings 从 left 到 right 填写最大值
     * 浪费空间多，但是方法简单
     * <p>
     * 思路一失败了，因为会超出 int 的最大值，用 2个数组来拼接来分段处理 接着用，但是没必要
     */
    class Solution {

        public List<List<Integer>> getSkyline(int[][] buildings) {
            if (buildings.length == 1) {
                return new ArrayList<>() {{
                    add(Arrays.asList(buildings[0][0], buildings[0][2]));
                    add(Arrays.asList(buildings[0][1], 0));
                }};
            }

            Map<Integer, Integer> pointMap = new HashMap<>();

            for (int i = 0; i < buildings.length; i++) {
                pointMap.put(buildings[i][0], pointMap.containsKey(buildings[i][0]) ? Math.max(pointMap.get(buildings[i][0]), buildings[i][2]) : buildings[i][2]);
                pointMap.put(buildings[i][1], pointMap.containsKey(buildings[i][1]) ? Math.max(pointMap.get(buildings[i][1]), buildings[i][2]) : buildings[i][2]);
            }

            List<Integer> pointList = new ArrayList<>(pointMap.keySet());

            Collections.sort(pointList);

            int i = 1;
            int size = pointList.size();
            // 遍历处理两侧都高不需要的点，只保留轮廓上的点
            while (i < size - 1) {
                int pre = pointMap.get(pointList.get(i - 1));
                int cur = pointMap.get(pointList.get(i));
                int next = pointMap.get(pointList.get(i + 1));
                if (cur <= pre && cur <= next) {
                    pointMap.remove(pointList.remove(i));
                    size--;
                } else {
                    i++;
                }
            }

            // 补充不连续的 x
            for (int j = 0; j < buildings.length-1; j++) {
                if (buildings[j][1] < buildings[j + 1][0]) {
//                    pointList.add(buildings[j][0]);
                    pointMap.put(buildings[j][1], 0);
                }
            }

            Collections.sort(pointList);

            i = 1;
            size = pointList.size();
            // 遍历轮廓点
            while (i < size) {
                int pre = pointMap.get(pointList.get(i - 1));
                int cur = pointMap.get(pointList.get(i));
                if (cur > pre) {
                    // 上升
                    if (Objects.equals(pointList.get(i - 1), pointList.get(i))) {
                        pointList.remove(i - 1);
                        size--;
                    }
                } else if (cur < pre) {
                    // 下降
                    pointMap.put(pointList.get(i - 1), cur);
                }
                i++;
            }

            // 补充结尾
            if (pointMap.get(pointList.get(pointList.size() - 1)) != 0) {
                pointMap.put(pointList.get(pointList.size() - 1), 0);
            }

            return pointList.stream().map(pi -> Arrays.asList(pi, pointMap.get(pi))).collect(Collectors.toList());
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q218_TheSkylineProblemBAK().new Solution();
        // TO TEST
//        System.out.println(solution.getSkyline((int[][]) ArrayUtil.genArrayByString("[[1,2,1],[1,2,2],[1,2,3]]")));
//        System.out.println(solution.getSkyline((int[][]) ArrayUtil.genArrayByString("[[0,2147483647,2147483647]]")));
        System.out.println(solution.getSkyline((int[][]) ArrayUtil.genArrayByString("[[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]")));
//        System.out.println(solution.getSkyline((int[][]) ArrayUtil.genArrayByString("[[0,2,3],[2,5,3]]")));
    }
}